GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Josephus-Problem</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Josephus-Problem</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Das Josephus-Problem oder die Josephus-Permutation ist ein theoretisches Problem aus der <a href="Informatik" title="Informatik">Informatik</a> oder <a href="Mathematik" title="Mathematik">Mathematik</a> (<a href="Kombinatorik" title="Kombinatorik">Kombinatorik</a>).

Es werden <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> nummerierte Objekte im Kreis angeordnet; dann wird, beginnend mit der Nummer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, jedes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">-te Objekt entfernt, wobei der Kreis immer wieder geschlossen wird. Die Reihenfolge der entfernten Objekte wird als Josephus-Permutation bezeichnet.

Ziel dieses Problems ist es, bei gegebenem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> das letzte Objekt der <a href="Permutation" title="Permutation">Permutation</a> zu bestimmen.

<div class="mw-heading mw-heading2"><h2 id="Geschichte">Geschichte</h2></div>

Das Problem wurde nach dem jüdischen Historiker <a href="Flavius_Josephus" title="Flavius Josephus">Flavius Josephus</a> benannt, welcher sich 67 n. Chr. beim Kampf um die <a href="Galil%C3%A4a" title="Galiläa">galiläische</a> Stadt <a href="Jotapata" title="Jotapata">Jotapata</a> mit 40 weiteren Männern in einer Höhle vor den Römern versteckt hielt (insgesamt also 41 Personen). Er berichtet darüber in seinem Buch <a href="J%C3%BCdischer_Krieg_(Flavius_Josephus)" title="Jüdischer Krieg (Flavius Josephus)">Jüdischer Krieg</a> (Buch 3, Kapitel 8). Als das Versteck verraten wurde, forderten die Römer sie auf, sich in Gefangenschaft zu ergeben. Seine Gefolgsleute zogen allerdings vor, durch <a href="Massenselbstt%C3%B6tung" title="Massenselbsttötung">kollektiven Suizid</a> zu sterben, wobei das Los über die Reihenfolge entschied. Durch Glück waren Josephus und ein weiterer Mann die Letzten und ergaben sich. Später wurde daraus eine <a href="Denksport" title="Denksport">Denksportaufgabe</a> gemacht, in dem sich alle im Kreis aufstellen und jeder 3. durch seinen rechten Nachbarn getötet werden sollte. Josephus stellte sich in diesem Spezialfall an die 16. Stelle, blieb damit als Vorletzter übrig und überwältigte den schwächeren Mann an der 31. Position. Beide ergaben sich den Römern und überlebten.

Nach <a href="Wilhelm_Ahrens_(Mathematiker)" title="Wilhelm Ahrens (Mathematiker)">Wilhelm Ahrens</a><a href="#cite_note-1">[1]</a> hat <a href="Gerolamo_Cardano" title="Gerolamo Cardano">Gerolamo Cardano</a> in seinem Werk Practica arithmeticae (1539) den Problemtyp Josephsspiel (Ludus Josephi) genannt, er war aber älter. Nach <a href="Moritz_Cantor" title="Moritz Cantor">Moritz Cantor</a><a href="#cite_note-2">[2]</a> findet es sich in der Handschrift von <a href="Nicolas_Chuquet" title="Nicolas Chuquet">Nicolas Chuquet</a> La triparty en la science des nombres (Lyon 1484). Das Problem wird auch von <a href="Claude_Gaspard_Bachet_de_M%C3%A9ziriac" title="Claude Gaspard Bachet de Méziriac">Claude Gaspard Bachet de Méziriac</a> (Problèmes plaisans et delectables, 1612) behandelt, der auch eine Variante angibt: 15 Türken und 15 Christen sind auf einem Schiff im Sturm. Der Kapitän muss 15 von ihnen opfern damit das Schiff nicht sinkt und lässt sie in einer Reihe aufstellen, wobei jeder neunte geopfert wird.

<div class="mw-heading mw-heading2"><h2 id="Lösung">Lösung</h2></div>

Das Problem wird hier gelöst für den Fall, dass jedes 2. Element entfernt wird (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0bd301789e1f25a3da4be297ff637754ebee5f5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=2}" loading="lazy">).

Für den allgemeinen Fall <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\neq 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\neq 2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/954372c73b10ed948c8ed9e269aaa91a751461a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.472ex; height:2.676ex;" alt="{\displaystyle k\neq 2}" loading="lazy"> folgt eine Lösung unten.

Die Lösung wird mittels Rekursion hergeleitet.

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c1c49fad1eccc4e9af1e4f23f32efdc3ac4da973.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.483ex; height:2.843ex;" alt="{\displaystyle f(n)}" loading="lazy"> bezeichne das letzte Element der Permutation, wenn anfangs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Elemente vorhanden waren (mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0bd301789e1f25a3da4be297ff637754ebee5f5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=2}" loading="lazy">).

Im ersten Durchlauf werden alle geradzahligen Elemente entfernt.

In der zweiten Runde werden die Elemente entfernt, die an der neuen 2., 4. usw. Position stehen, so als hätte es keine erste Runde gegeben.

Wenn die Anfangsanzahl von Elementen gerade ist,

dann war das Element <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> aus der zweiten Runde in der ersten Runde an Position <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2x-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2x-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75fc96485e02202cc2de34a26fe67d497bc51326.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.495ex; height:2.343ex;" alt="{\displaystyle 2x-1}" loading="lazy">.

Das Element <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(2n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(2n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e7e507c8be92db066188a6125d98e4a1194e8eef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.645ex; height:2.843ex;" alt="{\displaystyle f(2n)}" loading="lazy"> war ursprünglich auf Position <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2f(n)-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2f(n)-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8e91534dc75472559db1f6b9285fde3440b49a42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.648ex; height:2.843ex;" alt="{\displaystyle 2f(n)-1}" loading="lazy">. Das ergibt folgende Rekursionsformel:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(2n)=2f(n)-1.\,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/63cba7c7132f979712c995ce52ce6e7f9090ee04.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.425ex; height:2.843ex;" alt="{\displaystyle f(2n)=2f(n)-1.\,}" loading="lazy"></dd></dl>

Wenn die Elementanzahl anfangs ungerade ist, dann wird in der zweiten Runde

das ursprünglich erste Element entfernt, aber auch hier wird dann das neue 2.,

4. usw. Element entfernt. In diesem Fall ergibt sich, dass Element <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">

in der ersten Runde an Position <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2x+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2x+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec86c7ed988e98a84b2b33e07f0737a421bfba07.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.495ex; height:2.343ex;" alt="{\displaystyle 2x+1}" loading="lazy"> war. Daraus folgt die Rekursionsformel:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(2n+1)=2f(n)+1.\,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e330d5cffc42260a3818a38b9b66a4cb24103b43.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.428ex; height:2.843ex;" alt="{\displaystyle f(2n+1)=2f(n)+1.\,}" loading="lazy"></dd></dl>

Wenn man die Werte für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c1c49fad1eccc4e9af1e4f23f32efdc3ac4da973.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.483ex; height:2.843ex;" alt="{\displaystyle f(n)}" loading="lazy"> tabellarisch darstellt, sieht man ein Muster:

<table>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></td>

<td>16

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c1c49fad1eccc4e9af1e4f23f32efdc3ac4da973.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.483ex; height:2.843ex;" alt="{\displaystyle f(n)}" loading="lazy"></td>

<td>1

</td></tr></tbody></table>

Diese Tabelle lässt vermuten, dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c1c49fad1eccc4e9af1e4f23f32efdc3ac4da973.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.483ex; height:2.843ex;" alt="{\displaystyle f(n)}" loading="lazy"> eine aufsteigende Folge ungerader Zahlen ist,

welche wieder mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b18729f39cdba4b90c6c24c34cf558e826d0d1f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.744ex; height:2.843ex;" alt="{\displaystyle f(n)=1}" loading="lazy"> startet, wenn der Index <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> eine Zweierpotenz ist.

Wenn man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"> so wählt, dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2^{m}+l}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2^{m}+l}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b65df22179bdf0e35598d93bd6703a32c03100d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.864ex; height:2.509ex;" alt="{\displaystyle n=2^{m}+l}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq l<2^{m}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq l<2^{m}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d5189a60581e81a21347624a6b5ab932a9e59e4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.89ex; height:2.509ex;" alt="{\displaystyle 0\leq l<2^{m}}" loading="lazy">,

dann folgt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)=2\cdot l+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)=2\cdot l+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/42b018500733a6766ccf20d3ed652ae6336b73e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.119ex; height:2.843ex;" alt="{\displaystyle f(n)=2\cdot l+1}" loading="lazy">. Es ist offensichtlich, dass die Werte aus der Tabelle diese Gleichung erfüllen.

Nachfolgend erfolgt der Beweis durch <a href="Vollst%C3%A4ndige_Induktion" title="Vollständige Induktion">vollständige Induktion</a>.

Behauptung: Wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2^{m}+l}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2^{m}+l}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b65df22179bdf0e35598d93bd6703a32c03100d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.864ex; height:2.509ex;" alt="{\displaystyle n=2^{m}+l}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq l<2^{m}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq l<2^{m}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d5189a60581e81a21347624a6b5ab932a9e59e4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.89ex; height:2.509ex;" alt="{\displaystyle 0\leq l<2^{m}}" loading="lazy">, dann folgt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)=2l+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)=2l+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dd6d4a1f2b5a1513ce9ab10163bf23fc51d948ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.44ex; height:2.843ex;" alt="{\displaystyle f(n)=2l+1}" loading="lazy">.

Beweis: Vollständige Induktion über <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">. Der Fall <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d9ec7e1edc2e6d98f5aec2a39ae5f1c99d1e1425.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n=1}" loading="lazy"> ist wahr.

Man betrachte die Fälle für gerades <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> und ungerades <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> getrennt.

Wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> gerade, dann wähle man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/29b25eeca673386d676f79dce674fe93040693eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.748ex; height:2.509ex;" alt="{\displaystyle l_{1}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/31aafa60e48d39ccce922404c0b80340b2cc777a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.095ex; height:2.009ex;" alt="{\displaystyle m_{1}}" loading="lazy"> so, dass

</mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n/2=2^{m_{1}}+l_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2fd6343010fb386af17a62856fd112676a3f7aa1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.075ex; height:2.843ex;" alt="{\displaystyle n/2=2^{m_{1}}+l_{1}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq l_{1}<2^{m_{1}}}">

<msub>

</mrow>

</msub>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq l_{1}<2^{m_{1}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cae73db595a655f9cc9f0b5b9652efff28a5d116.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.776ex; height:2.676ex;" alt="{\displaystyle 0\leq l_{1}<2^{m_{1}}}" loading="lazy">. Es gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l_{1}=l/2}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l_{1}=l/2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/069aa97d0fcecc250f0ac344c3ffc01c9c4d7054.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.864ex; height:2.843ex;" alt="{\displaystyle l_{1}=l/2}" loading="lazy">.

Wir haben <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1}">

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6639ae83b9b9f50201326c0ff41ee1ef340325e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:47.306ex; height:2.843ex;" alt="{\displaystyle f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1}" loading="lazy">, bei der die zweite Gleichung aus der Induktionsannahme folgt.

Wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ungerade, dann wähle man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/29b25eeca673386d676f79dce674fe93040693eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.748ex; height:2.509ex;" alt="{\displaystyle l_{1}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/31aafa60e48d39ccce922404c0b80340b2cc777a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.095ex; height:2.009ex;" alt="{\displaystyle m_{1}}" loading="lazy"> so, dass

</mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n-1)/2=2^{m_{1}}+l_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8ba574aedbde4c8bec87cce8a667eeedb84f7c58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.887ex; height:2.843ex;" alt="{\displaystyle (n-1)/2=2^{m_{1}}+l_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq l_{1}<2^{m_{1}}}">

<msub>

</mrow>

</msub>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq l_{1}<2^{m_{1}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cae73db595a655f9cc9f0b5b9652efff28a5d116.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.776ex; height:2.676ex;" alt="{\displaystyle 0\leq l_{1}<2^{m_{1}}}" loading="lazy">. Es gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l_{1}=(l-1)/2}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l_{1}=(l-1)/2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b3f92739fc3811f2524009abb54af4a1b4a1ee1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.676ex; height:2.843ex;" alt="{\displaystyle l_{1}=(l-1)/2}" loading="lazy">.

Wir haben <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1}">

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/405c97bca01969df4cefd7d3e926921433723f59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:53.118ex; height:2.843ex;" alt="{\displaystyle f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1}" loading="lazy">, bei der die zweite Gleichung ebenfalls aus der Induktionsannahme folgt.

Damit ist die Behauptung bewiesen.

Die eleganteste Form der Lösung folgt aus der binären Repräsentation von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c1c49fad1eccc4e9af1e4f23f32efdc3ac4da973.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.483ex; height:2.843ex;" alt="{\displaystyle f(n)}" loading="lazy"> kann durch eine 1-Bit-Linksrotation von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> selbst ermittelt werden.

Wenn man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> binär als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=b_{0}b_{1}b_{2}b_{3}\dots b_{m}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=b_{0}b_{1}b_{2}b_{3}\dots b_{m}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/79f8fbd8071e6850d1981f23a8b1e73aac0eb208.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.87ex; height:2.509ex;" alt="{\displaystyle n=b_{0}b_{1}b_{2}b_{3}\dots b_{m}}" loading="lazy"> repräsentiert,

dann ist die Lösung gegeben als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)=b_{1}b_{2}b_{3}\dots b_{m}b_{0}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)=b_{1}b_{2}b_{3}\dots b_{m}b_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/babd7a5d8f31075beb5d019da54850a2ce741434.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.958ex; height:2.843ex;" alt="{\displaystyle f(n)=b_{1}b_{2}b_{3}\dots b_{m}b_{0}}" loading="lazy">.

Der Beweis folgt aus der Repräsentation von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{m}+l}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{m}+l}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d5d47762830148c6b6f105d00392799cdf85b82f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.371ex; height:2.509ex;" alt="{\displaystyle 2^{m}+l}" loading="lazy">.

In geschlossener Form lautet die Lösung für den Fall <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0bd301789e1f25a3da4be297ff637754ebee5f5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=2}" loading="lazy">:<a href="#cite_note-3">[3]</a>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n)=1+2n-2^{1+\lfloor \log _{2}n\rfloor }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2297fc517ec0590697294324173a4d75de8dd928.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.243ex; height:3.343ex;" alt="{\displaystyle f(n)=1+2n-2^{1+\lfloor \log _{2}n\rfloor }}" loading="lazy"></dd></dl>

mit der <a href="Gau%C3%9Fklammer" class="mw-redirect" title="Gaußklammer">Gaußklammer</a> (Abrundungsfunktion) <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lfloor \dots \rfloor }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lfloor \dots \rfloor }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5acd138a719029b298d766f7c5046d049149f57c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.788ex; height:2.843ex;" alt="{\displaystyle \lfloor \dots \rfloor }" loading="lazy">

Es gibt auch eine Lösung in geschlossener Form für den Fall <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=3}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/662e06a2436f8a44fec791f5c794621f10dc8f30.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=3}" loading="lazy">.<a href="#cite_note-4">[4]</a>

Die <a href="Dynamische_Programmierung" title="Dynamische Programmierung">dynamische Programmierung</a> ist der einfachste Weg, dieses Problem für den allgemeinen Fall zu lösen.

Diese Methode verwendet die Rekursionsformel:

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(n,k)=(f(n-1,k)+k){\bmod {n}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4f947f6a0291e8e7c3a081a681adb02b90f5363.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.494ex; height:2.843ex;" alt="{\displaystyle f(n,k)=(f(n-1,k)+k){\bmod {n}}}" loading="lazy">, mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(1,k)=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(1,k)=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d457c06f610d16ff3a5eff7365de3b680bdfa37b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.756ex; height:2.843ex;" alt="{\displaystyle f(1,k)=1}" loading="lazy"></dd></dl>

welche offensichtlich ist, wenn man berücksichtigt, wie sich die Nummer des letzten Elements ändert,

wenn man von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fbd0b0f32b28f51962943ee9ede4fb34198a2521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}" loading="lazy"> nach <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> wechselt.

Diese Methode hat eine <a href="O-Notation" class="mw-redirect" title="O-Notation">Laufzeit</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy">,

aber für kleine <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> und große <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> gibt es einen anderen Ansatz.

Dieser zweite Ansatz verwendet auch die dynamische Programmierung,

erfordert aber nur eine Laufzeit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(k\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(k\log n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5dcf3e2dc7b376b4d26d7574a5dced51ca5909df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.934ex; height:2.843ex;" alt="{\displaystyle O(k\log n)}" loading="lazy">.

Er entfernt die k., 2k., …, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lfloor n/k\rfloor }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lfloor n/k\rfloor }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/037c0f5b75e24bd4b4680f5d9feefd0761e2dc4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.833ex; height:2.843ex;" alt="{\displaystyle \lfloor n/k\rfloor }" loading="lazy">.

Elemente in einem Schritt und ändert dann die Nummerierung.

<div class="mw-heading mw-heading2"><h2 id="Implementierung">Implementierung</h2></div>

Der folgende Algorithmus realisiert das Problem <a href="Rekursive_Programmierung" title="Rekursive Programmierung">rekursiv</a> nach der obigen Rekursionsformel für den Fall k=2 und besitzt eine Laufzeit von O(log(n)).

<pre>int josephus(int n)

{

if(n == 1)

return 1;

if((n%2) == 0)

return 2 * josephus(n / 2) - 1;

if((n%2) == 1)

return 2 * josephus((n - 1) / 2) + 1;

}

</pre>

Gemäß der geschlossenen Formel f(n)=2*l + 1 lässt sich der folgende nicht-rekursive Algorithmus angeben. Seine Laufzeit liegt in O(1).

<pre>int josephus(int n)

{

m = floor( log2(n) );

l = n - 2^m;

j = 2*l + 1;

return j;

}

</pre>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Paul Yiu: Recreational Mathematics, Florida Atlantic University: Department of Mathematics <a rel="nofollow" class="external text" href="http://www.math.fau.edu/yiu/RecreationalMathematics2003.pdf">(Als PDF in englischer Sprache verfügbar; 868 kB)</a></li>

<li><a href="Walter_William_Rouse_Ball" class="mw-redirect" title="Walter William Rouse Ball">Walter William Rouse Ball</a>, <a href="Harold_Scott_Macdonald_Coxeter" class="mw-redirect" title="Harold Scott Macdonald Coxeter">Harold Scott Macdonald Coxeter</a>: Mathematical Recreations and Essays, Dover, 1987. Seiten 32–36, ISBN 0-486-25357-0</li>

<li><a href="Ronald_Graham" title="Ronald Graham">Ronald L. Graham</a>, <a href="Donald_E._Knuth" title="Donald E. Knuth">Donald E. Knuth</a> und <a href="Oren_Patashnik" title="Oren Patashnik">Oren Patashnik</a>: <a href="Concrete_Mathematics" title="Concrete Mathematics">Concrete Mathematics: A Foundation for Computer Science</a>, Massachusetts, 1994. Seiten 8–16, ISBN 978-0-201-55802-9</li>

<li>James Dowdy, Michael E. Mays: Josephus Permutations, Journal of Combinatorial Mathematics and Combinatorial Computing, Band 6, 1989, S. 125–130</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li>Lorenz J. Halbeisen: <a rel="nofollow" class="external text" href="https://people.math.ethz.ch/~halorenz/publications/pdf/jos.pdf">The Josephus Problem.</a> Abgerufen im 1. Januar 1<span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3AJosephus-Problem&rft.title=The+Josephus+Problem&rft.description=The+Josephus+Problem&rft.identifier=&rft.creator=Lorenz+J.%26%2332%3BHalbeisen&rft.date="> </li>

<li><a rel="nofollow" class="external text" href="http://www.cut-the-knot.org/recurrence/flavius.shtml">Josephus Flavius game</a> bei Cut-the-knot</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> Ahrens, Mathematische Unterhaltungen und Spiele, Teubner 1901, Kapitel 15, S. 286ff

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> Moritz Cantor, Vorlesungen über die Geschichte der Mathematik, Band 2, S. 332

</li>

<li id="cite_note-3"><a href="#cite_ref-3">↑</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/JosephusProblem.html">Josephus problem</a>, Mathworld

</li>

<li id="cite_note-4"><a href="#cite_ref-4">↑</a> Lorenz Halbeisen, <a href="Norbert_Hungerb%C3%BChler" title="Norbert Hungerbühler">Norbert Hungerbühler</a>: The Josephus Problem, J. Théor. Nombres Bordeaux, Band 9, 1976, S. 303–318

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-11-11" href="https://de.wikipedia.org/wiki/?title=Josephus-Problem&oldid=261465032">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>